package puzzle.projecteuler.p300;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

/**
 * you should set vm parameters: -Xms768m -Xmx1024m
 * the code can be refined.
 * @author wong tong
 *
 */
public class Problem204C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Integer[] ps = {
				 2,    3,    5,    7,   11,   13,   17,   19,   
				23,   29,   31,   37,   41,   43,   47,   53,   
				59,   61,   67,   71,   73,   79,   83,   89,   
				97
		};
		BigInteger max = BigInteger.valueOf(10).pow(9);
		Set<BigInteger> s = calc(max, ps);
		System.out.println(s.size());
	}

	private static Set<BigInteger> calc(BigInteger max, Integer[] ps) {

		int max_p = ps[ps.length-1];
		int max_pow = (int)Math.floor(Math.log(max.doubleValue())/Math.log(max_p));
		
		int n = ps.length;
		if (n == 1) {
			Set<BigInteger> s = new HashSet<BigInteger>();
			for (int i = 0; i <= max_pow; i ++) {
				BigInteger a = BigInteger.valueOf(max_p).pow(i);
				if (a.compareTo(max) != 1) {
					s.add(a);
				}
			}
			return s;
		} else {
			Integer[] newPs = new Integer[n-1];
			System.arraycopy(ps, 0, newPs, 0, n-1);
			Set<BigInteger> s = new HashSet<BigInteger>();
			for (int i = 0; i <= max_pow; i ++) {
				BigInteger a = BigInteger.valueOf(max_p).pow(i);
				BigInteger newMax = max.divide(a);
				Set<BigInteger> t = calc(newMax, newPs);
				for (BigInteger b: t) {
					BigInteger c = b.multiply(a);
					if (c.compareTo(max) != 1) {
						s.add(c);
					}
				}
			}
			return s;
		}
	}
}
